//
//  SGHMedianFind.m
//  ObjectiveCDemo20200321
//
//  Created by 远平 on 2021/11/25.
//  Copyright © 2021 远平. All rights reserved.
//

#import "SGHMedianFind.h"

@implementation SGHMedianFind

- (void)test {
    int a[10] = {59,20,17,36,98,14,23,83,13,28};
    int mid = findMedian(a, 10);
    NSLog(@"中位数为：%d",mid);
}

int findMedian(int a[], int n) {
    int low = 0;
    int high = n - 1;
    int mid = (n - 1) / 2;
    int div = PartSort(a, low, high);
    
    while (div != mid) {
        if (mid < div) {
            //左半区间找
            div = PartSort(a, low, div - 1);
        } else {
            //右半区间找
            div = PartSort(a, div + 1, high);
        }
    }
    //找到了
    return a[mid];
    
}
int PartSort(int a[], int start, int end) {
    int i = start;
    int j = end;
    //选取关键字
    int key = a[end];
    while (i < j) {
        //左边找比key大的值
        while (i < j && a[i] <= key) {
            ++i;
        }
        //右边找比key小的值
        while (i < j && a[j] >= key) {
            --j;
        }
        if (i < j) {
            //找到之后交换左右的值
            int temp = a[i];
            a[i] = a[j];
            a[j] = temp;
        }
    }
    int temp = a[j];
    a[j] = a[end];
    a[end] = temp;
    
    return i;
}

@end
